package com.sk.leetcode.arithmetic;

/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * 示例:
 * 输入:
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 */
public class Test23 {
    public static void main(String[] args) {
        int[][] intss = {{}, {-1, 5, 11}, {}, {6, 10}};
        ListNode[] lists = new ListNode[intss.length];
        int index = 0;

        for (int[] ints : intss) {
            ListNode listNode = null;
            boolean b = true;
            for (int i = 0; i < ints.length; i++) {
                b = false;
                ListNode node = new ListNode(ints[i]);
                if(i == 0) {
                    lists[index++] = node;
                    listNode = node;
                } else {
                    listNode.next = node;
                    listNode = node;
                }
            }
            if(b) {
                lists[index++] = listNode;
            }
        }
        //ListNode[] listse = {new ListNode(1)};
        ListNode listNode = mergeKLists(lists);
        System.out.println(listNode.val);
        while ((listNode = listNode.next) != null) {
            System.out.println(listNode.val);
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) {
            return null;
        }
        if(lists.length == 1) {
            return lists[0];
        }
        int index = 0, indexEnd = lists.length - 1;
        while (true) {
            ListNode node1 = lists[index];
            ListNode nodeq = null;
            ListNode node2 = lists[indexEnd];

            boolean b = true;
            if(node1 == null) {
                lists[index] = node2;
                b = false;
            }
            if(node2 == null) {
                b = false;
            }
            while (b) {
                if(node1.val >= node2.val) {
                    if(nodeq == null) {
                        nodeq = node2;
                        node2 = node2.next;
                        nodeq.next = node1;
                        lists[index] = nodeq;
                    } else {
                        ListNode lin = node2.next;
                        nodeq.next = node2;
                        node2.next = node1;
                        node2 = lin;
                        nodeq = nodeq.next;
                    }
                } else {
                    nodeq = node1;
                    node1 = node1.next;
                }
                if(node2 == null) {
                    b = false;
                }
                if(node1 == null) {
                    nodeq.next = node2;
                    b = false;
                }
            }
            index++;
            indexEnd--;
            if(indexEnd == 0) {
                return lists[0];
            }
            if(index >= indexEnd) {
                index = 0;
            }
        }


    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}